import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class labyrinth {
    /*从0,0位置进入一个M行N列的藏宝迷宫, 从入口位置顺时针螺旋前进知道到达迷宫中心,
    每格上都有不同价值的珠宝, 收集的珠宝价值大于W时出现迷宫出口, 请输出出口位置i,j.
    无法收集到足够的则输出-1.
    第一行输入包括M,N,W,用空格分隔, 接下来M行分别表示对应位置的珠宝价值,用空格分隔*/
    //螺旋遍历迷宫
    public static int[] telabyrunth(int[][] matrix,int w){
        List<Integer> res = new ArrayList<>();
        if(matrix == null || matrix.length == 0){
            return new int[]{-1};
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int upperBound = 0,downBound = m - 1;
        int leftBound = 0,rightBound = n - 1;
        int collectedValue = 0;
        while(res.size() < m * n){
            if(upperBound <= downBound){
                for (int i = leftBound; i <= rightBound; i++) {
                    collectedValue +=
                            matrix[upperBound][i];
                    if(collectedValue > w){
                        return new int[]{upperBound,i};
                    }
                }
                upperBound++;
            }
            if(leftBound <= rightBound){
                for (int i = upperBound; i <= downBound; i++) {
                    collectedValue +=
                            matrix[i][rightBound];
                    if(collectedValue > w){
                        return new int[]{i,rightBound};
                    }
                }
                rightBound--;
            }
            if(upperBound <= downBound){
                for (int i = rightBound; i >= leftBound ; i--) {
                    collectedValue +=
                            matrix[downBound][i];
                    if(collectedValue > w){
                        return new int[]{downBound,i};
                    }
                }
                downBound--;
            }
            if(leftBound <= rightBound){
                for (int i = downBound; i >= upperBound ; i--) {
                    collectedValue +=
                            matrix[i][leftBound];
                    if(collectedValue > w){
                        return new int[]{i,leftBound};
                    }
                }
                leftBound++;
            }
        }
        return new int[]{-1};
    }
}
